import heapq
from typing import List


class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
        length = len(nums1)
        # heapq是小根堆，插入元组时，默认使用元组的第一个元素作为优先级
        maxHeap = [(-val, index) for index, val in enumerate(nums2)]
        heapq.heapify(maxHeap)
        nums1.sort()
        left, right = 0, length - 1
        res = [0] * length
        # 使用heapq模块创建的堆是一个列表，因此可以像检查普通列表一样检查堆是否为空。
        # 可以通过检查列表的长度来确定堆是否为空。如果堆的长度为0，则表示堆为空。
        while maxHeap:
            val, index = heapq.heappop(maxHeap)
            if nums1[right] > -val :
                res[index] = nums1[right]
                right -= 1
            else:
                res[index] = nums1[left]
                left += 1
        return res